#include "game.h"
#include "game_platform.h"
#include "game_sort.h"
inline void Swap(sort_entry *A, sort_entry *B) {
    sort_entry Temp = *B;
    *B = *A;
    *A = Temp;
}

void MergeSort(uint32 Count, sort_entry *First, sort_entry *Temp) {
    if (Count == 1) {
    } else if (Count == 2) {
        sort_entry *EntryA = First;
        sort_entry *EntryB = First + 1;
        if (EntryA->SortKey > EntryB->SortKey) {
            Swap(EntryA, EntryB);
        }
    } else {
        uint32 Half0 = Count / 2;
        uint32 Half1 = Count - Half0;
        Assert(Half0 >= 1);
        Assert(Half1 >= 1);
        sort_entry *InHalf0 = First;
        sort_entry *InHalf1 = First + Half0;
        sort_entry *End = First + Count;

        MergeSort(Half0, InHalf0, Temp);
        MergeSort(Half1, InHalf1, Temp);

        sort_entry *ReadHalf0 = InHalf0;
        sort_entry *ReadHalf1 = InHalf1;

        sort_entry *Out = Temp;

        for (uint32 Index = 0; Index < Count; Index++) {
            if (ReadHalf0 == InHalf1) {
                *Out++ = *ReadHalf1++;
            } else if (ReadHalf1 == End) {
                *Out++ = *ReadHalf0++;
            } else if (ReadHalf0->SortKey < ReadHalf1->SortKey) {
                *Out++ = *ReadHalf0++;
            } else {
                *Out++ = *ReadHalf1++;
            }
        }

        for (uint32 Index = 0; Index < Count; ++Index) {
            First[Index] = Temp[Index];
        }

#if 0

        sort_entry *ReadHalf0 = First;
        sort_entry *ReadHalf1 = First + Half0;
        sort_entry *End = First + Count;

        while ((ReadHalf0 != ReadHalf1) && (ReadHalf0->SortKey < ReadHalf1->SortKey)) {
            ++ReadHalf0;
        }
        if (ReadHalf0 != ReadHalf1) {
            sort_entry CompareWith = *ReadHalf0;
            while ((ReadHalf1 != End) && (ReadHalf1->SortKey < CompareWith.SortKey)) {
                Swap(ReadHalf0++, ReadHalf1++);
            }
            ReadHalf1 = InHalf1;
        }
#endif
    }
}

void BubbleSort(uint32 Count, sort_entry *First, sort_entry *Temp) {
    (void)Temp;
    for (uint32 Outer = 0; Outer < Count; ++Outer) {
        bool ListIsSorted = true;
        for (uint32 Inner = 0; Inner < (Count - 1); ++Inner) {
            sort_entry *EntryA = First + Inner;
            sort_entry *EntryB = EntryA + 1;
            if (EntryA->SortKey > EntryB->SortKey) {
                Swap(EntryA, EntryB);
                ListIsSorted = false;
            }
        }
        if (ListIsSorted) {
            break;
        }
    }
}
inline uint32 SortKeyToUint32(real32 SortKey) {
    uint32 Result = *(uint32 *)&SortKey;
    if (Result & 0x80000000) {
        Result = ~Result;
    } else {
        Result |= 0x80000000;
    }
    return Result;
}

void RadixSort(uint32 Count, sort_entry *First, sort_entry *Temp) {
    sort_entry *Source = First;
    sort_entry *Dest = Temp;
    for (uint32 ByteIndex = 0; ByteIndex < 32; ByteIndex += 8) {
        uint32 SortKeyOffset[256] = {};
        // 第一遍遍历 —— 统计每种键值的数量
        for (uint32 Index = 0; Index < Count; ++Index) {
            uint32 RadixValue = SortKeyToUint32(Source[Index].SortKey);
            uint32 RadixPiece = (RadixValue >> ByteIndex) & 0xFF;
            ++SortKeyOffset[RadixPiece];
        }
        // 将计数转换为偏移量
        uint32 Total = 0;
        for (uint32 SortKeyIndex = 0; SortKeyIndex < ArrayCount(SortKeyOffset); ++SortKeyIndex) {
            uint32 KeyCount = SortKeyOffset[SortKeyIndex];
            SortKeyOffset[SortKeyIndex] = Total;
            Total += KeyCount;
        }
        // 第二遍遍历 —— 将元素放置到正确的位置
        for (uint32 Index = 0; Index < Count; ++Index) {
            uint32 RadixValue = SortKeyToUint32(Source[Index].SortKey);
            uint32 RadixPiece = (RadixValue >> ByteIndex) & 0xFF;
            Dest[SortKeyOffset[RadixPiece]++] = Source[Index];
        }
        sort_entry *SwapTemp = Dest;
        Dest = Source;
        Source = SwapTemp;
    }
}
inline bool32 IsInFrontOf(sprite_bound A, sprite_bound B);
#if 0
uint32 *SortEntries(game_render_commands *Commands, memory_arena *TempArena,
                    game_render_prep *Prep) {
    TIMED_FUNCTION();
    uint32 Count = Commands->SortEntryCount;
    uint32 *Result = PushArray(TempArena, Count, uint32);
    sort_sprite_bound *Entries = GetSortEntries(Commands);
#if 1
    sprite_graph_walk Walk = {};
    Walk.OutIndex = Result;

    for (uint32 FirstIndex = 0; FirstIndex < Count;) {
        sort_sprite_bound *SubEntries = Entries + FirstIndex;
        uint32 SubCount = BuildSpriteGraph(Count - FirstIndex,  //
                                           SubEntries,          //
                                           TempArena, Commands->Width, Commands->Height);
        Walk.InputNodes = SubEntries;
        for (uint32 NodexIndexA = 0; NodexIndexA < SubCount; ++NodexIndexA) {
            Walk.HitCycle = false;
            RecursiveFontToBack(&Walk, NodexIndexA);
        }
        FirstIndex += SubCount + 1;
    }
    Prep->SortedIndices = Result;
    Prep->SortedIndexCount = (uint32)(Walk.OutIndex - Result);
#else
    for (uint32 NodeIndexA = 0; NodeIndexA < Count; ++NodeIndexA) {
        Result[NodeIndexA] = Entries[NodeIndexA].Index;
    }
#endif
#if 0
    if (Count) {
#if 1
        // RadixSort(Count, Entries, (sort_sprite_bound *)SortMemory);
        MergeSort(Count, Entries, (sort_sprite_bound *)SortMemory);

#else
        MergeSort(Count, Entries, SortMemory);
#endif
#if GAME_SLOW
        for (uint32 Index = 0; Index < (Count - 1); ++Index) {
#if 1
            uint32 IndexB = Index + 1;
            {
#else
            for (uint32 IndexB = 0; IndexB < Count; ++IndexB) {
#endif
                sort_sprite_bound *EntryA = Entries + Index;
                sort_sprite_bound *EntryB = EntryA + IndexB;
                if (IsInFrontOf(EntryA->SortKey, EntryB->SortKey)) {
#if 1
                    Assert((EntryA->SortKey.YMin == EntryB->SortKey.YMin) &&
                           (EntryA->SortKey.YMax == EntryB->SortKey.YMax) &&
                           (EntryA->SortKey.ZMax == EntryB->SortKey.ZMax))
#else
                    ++SortError;
#endif
                }
            }
        }
    }
#endif  // GAME_SLOW
#endif
    return Result;
}
#endif
uint32 UnsortedOutput(sprite_graph_walk *Walk, uint32 InputNodeCount,
                      sort_sprite_bound *InputNodes) {
    uint32 NodeIndexA = 0;
    for (; NodeIndexA < InputNodeCount; ++NodeIndexA) {
        sort_sprite_bound *A = InputNodes + NodeIndexA;
        if (A->Offset == SPRITE_BARRIER_OFFSET_VALUE) {
            break;
        }
        Assert(A->Flags == 0);
        *Walk->OutIndex++ = A->Offset;
    }
    return NodeIndexA;
}

uint32 *SortEntries(game_render_commands *Commands, memory_arena *TempArena,
                    game_render_prep *Prep) {
    TIMED_FUNCTION();
    uint32 Count = Commands->SortEntryCount;
    uint32 *Result = PushArray(TempArena, Count, uint32);
    sort_sprite_bound *Entries = GetSortEntries(Commands);
#if 1
    sprite_graph_walk Walk = {};
    Walk.OutIndex = Result;
    bool32 ShouldSort = true;
    for (uint32 FirstIndex = 0; FirstIndex < Count;) {
        sort_sprite_bound *SubEntries = Entries + FirstIndex;
        uint32 SubCount = 0;
        if (ShouldSort) {
            SubCount = BuildSpriteGraph(Count - FirstIndex,  //
                                        SubEntries,          //
                                        TempArena, Commands->Width, Commands->Height);
            Walk.InputNodes = SubEntries;
            for (uint32 NodexIndexA = 0; NodexIndexA < SubCount; ++NodexIndexA) {
                Walk.HitCycle = false;
                RecursiveFontToBack(&Walk, NodexIndexA);
            }
        } else {
            SubCount = UnsortedOutput(&Walk, Count - FirstIndex, SubEntries);
        }
        sort_sprite_bound *Terminator = SubEntries + SubCount;
        FirstIndex += SubCount + 1;
        if (FirstIndex < Count) {
            ShouldSort = !((Terminator->Flags & Sprite_BarrierTurnsOffSorting));
        }
    }
    Prep->SortedIndices = Result;
    Prep->SortedIndexCount = (uint32)(Walk.OutIndex - Result);
#else
    for (uint32 NodeIndexA = 0; NodeIndexA < Count; ++NodeIndexA) {
        Result[NodeIndexA] = Entries[NodeIndexA].Index;
    }
#endif
#if 0
    if (Count) {
#if 1
        // RadixSort(Count, Entries, (sort_sprite_bound *)SortMemory);
        MergeSort(Count, Entries, (sort_sprite_bound *)SortMemory);

#else
        MergeSort(Count, Entries, SortMemory);
#endif
#if GAME_SLOW
        for (uint32 Index = 0; Index < (Count - 1); ++Index) {
#if 1
            uint32 IndexB = Index + 1;
            {
#else
            for (uint32 IndexB = 0; IndexB < Count; ++IndexB) {
#endif
                sort_sprite_bound *EntryA = Entries + Index;
                sort_sprite_bound *EntryB = EntryA + IndexB;
                if (IsInFrontOf(EntryA->SortKey, EntryB->SortKey)) {
#if 1
                    Assert((EntryA->SortKey.YMin == EntryB->SortKey.YMin) &&
                           (EntryA->SortKey.YMax == EntryB->SortKey.YMax) &&
                           (EntryA->SortKey.ZMax == EntryB->SortKey.ZMax))
#else
                    ++SortError;
#endif
                }
            }
        }
    }
#endif
#endif
    return Result;
}

inline bool32 IsInFrontOf(sprite_bound A, sprite_bound B) {
#if 1
    bool32 Result;
    if (A.ChunkZ != B.ChunkZ) {
        Result = (A.ChunkZ > B.ChunkZ);
    } else if ((A.ManualSort.AlwaysInFrontOf != 0) &&
               (A.ManualSort.AlwaysInFrontOf == B.ManualSort.AlwaysBehind)) {
        Result = true;
    } else if ((A.ManualSort.AlwaysBehind != 0) &&
               (A.ManualSort.AlwaysBehind == B.ManualSort.AlwaysInFrontOf)) {
        Result = false;
    } else {
        bool32 BothZSprites = ((A.YMin != A.YMax) && (B.YMin != B.YMax));
        bool32 AIncludesB = (B.YMin >= A.YMin) && (B.YMin <= A.YMax);
        bool32 BIncludesA = (A.YMin >= B.YMin) && (A.YMin <= B.YMax);
        bool32 SortByZ = (BothZSprites || AIncludesB || BIncludesA);
        Result = (SortByZ ? (A.ZMax > B.ZMax) : (A.YMin < B.YMin));
    }
#endif
    return Result;
}

inline bool32 IsInFrontOfY(sprite_bound A, sprite_bound B) {
    bool32 Result = A.YMin < B.YMin;
    return Result;
}

inline bool32 IsInFrontOfZ(sprite_bound A, sprite_bound B) {
    bool32 Result = A.ZMax > B.ZMax;
    return Result;
}

inline void Swap(sort_sprite_bound *A, sort_sprite_bound *B) {
    sort_sprite_bound Temp = *B;
    *B = *A;
    *A = Temp;
}

bool32 IsZSprite(sprite_bound Bound) {
    bool32 Result = (Bound.YMin != Bound.YMax);
    return Result;
}

internal void VerifyBuffer(uint32 Count, sort_sprite_bound *Buffer, bool32 ZSprite) {
    for (uint32 Index = 0; Index < Count; ++Index) {
        Assert(IsZSprite(Buffer[Index].SortKey) == ZSprite);
        if (Index > 0) {
            Assert(IsInFrontOf(Buffer[Index].SortKey, Buffer[Index - 1].SortKey));
        }
    }
}

void SeparatedMergeSort(uint32 Count, sort_sprite_bound *First, sort_sprite_bound *Temp) {
    uint32 YCount = 0;
    uint32 ZCount = 0;
    for (uint32 Index = 0; Index < Count; ++Index) {
        sort_sprite_bound *This = First + Index;
        if (IsZSprite(This->SortKey)) {
            Temp[ZCount++] = *This;
        } else {
            First[YCount++] = *This;
        }
    }
#if GAME_SLOW
    VerifyBuffer(YCount, First, false);
    VerifyBuffer(ZCount, Temp, true);
#endif
    MergeSort(YCount, First, Temp + ZCount);
    MergeSort(ZCount, Temp, First + YCount);
    if (YCount == 1) {
        Temp[ZCount] = First[0];
    } else if (YCount == 2) {
        Temp[ZCount] = First[0];
        Temp[ZCount + 1] = First[1];
    }

    sort_sprite_bound *InHalf0 = Temp;
    sort_sprite_bound *InHalf1 = Temp + ZCount;
#if GAME_SLOW
    VerifyBuffer(YCount, InHalf1, false);
    VerifyBuffer(ZCount, InHalf0, true);
#endif
    sort_sprite_bound *End = InHalf1 + YCount;
    sort_sprite_bound *ReadHalf0 = InHalf0;
    sort_sprite_bound *ReadHalf1 = InHalf1;

    sort_sprite_bound *Out = First;

    for (uint32 Index = 0; Index < Count; Index++) {
        if (ReadHalf0 == InHalf1) {
            *Out++ = *ReadHalf1++;
        } else if (ReadHalf1 == End) {
            *Out++ = *ReadHalf0++;
        } else if (IsInFrontOf(ReadHalf1->SortKey, ReadHalf0->SortKey)) {
            *Out++ = *ReadHalf0++;
        } else {
            *Out++ = *ReadHalf1++;
        }
    }
    Assert(Out == (First + Count));
    Assert(ReadHalf0 == InHalf1);
    Assert(ReadHalf1 == End);
}
void MergeSort(uint32 Count, sort_sprite_bound *First, sort_sprite_bound *Temp) {
    if (Count == 1) {
    } else if (Count == 2) {
        sort_sprite_bound *EntryA = First;
        sort_sprite_bound *EntryB = First + 1;
        if (IsInFrontOf(EntryA->SortKey, EntryB->SortKey)) {
            Swap(EntryA, EntryB);
        }
    } else {
        uint32 Half0 = Count / 2;
        uint32 Half1 = Count - Half0;
        Assert(Half0 >= 1);
        Assert(Half1 >= 1);
        sort_sprite_bound *InHalf0 = First;
        sort_sprite_bound *InHalf1 = First + Half0;
        sort_sprite_bound *End = First + Count;

        MergeSort(Half0, InHalf0, Temp);
        MergeSort(Half1, InHalf1, Temp);

        sort_sprite_bound *ReadHalf0 = InHalf0;
        sort_sprite_bound *ReadHalf1 = InHalf1;

        sort_sprite_bound *Out = Temp;

        for (uint32 Index = 0; Index < Count; Index++) {
            if (ReadHalf0 == InHalf1) {
                *Out++ = *ReadHalf1++;
            } else if (ReadHalf1 == End) {
                *Out++ = *ReadHalf0++;
            } else if (IsInFrontOf(ReadHalf1->SortKey, ReadHalf0->SortKey)) {
                *Out++ = *ReadHalf0++;
            } else {
                *Out++ = *ReadHalf1++;
            }
        }

        for (uint32 Index = 0; Index < Count; ++Index) {
            First[Index] = Temp[Index];
        }
    }
}

bool32 GetGridSpan(rectangle2 TotalScreen, v2 InvCellDim, rectangle2 Source, rectangle2i *Dest) {
    v2 MinR = Hadamard(InvCellDim, GetMinCorner(Source));
    v2 MaxR = Hadamard(InvCellDim, GetMaxCorner(Source));
    Dest->MinX = TruncateReal32ToUInt32(MinR.x);
    Dest->MinY = TruncateReal32ToUInt32(MinR.y);
    Dest->MaxX = TruncateReal32ToUInt32(MaxR.x);
    Dest->MaxY = TruncateReal32ToUInt32(MaxR.y);
    bool32 Inside = RectanglesIntersect(TotalScreen, Source);
    if (Inside) {
        if (Dest->MinX < 0) {
            Dest->MinX = 0;
        }
        if (Dest->MinX >= SORT_GRID_WIDTH) {
            Dest->MinX = (SORT_GRID_WIDTH - 1);
        }
        if (Dest->MinY < 0) {
            Dest->MinY = 0;
        }
        if (Dest->MinY >= SORT_GRID_HEIGHT) {
            Dest->MinY = (SORT_GRID_HEIGHT - 1);
        }

        if (Dest->MaxX < 0) {
            Dest->MaxX = 0;
        }
        if (Dest->MaxX >= SORT_GRID_WIDTH) {
            Dest->MaxX = (SORT_GRID_WIDTH - 1);
        }
        if (Dest->MaxY < 0) {
            Dest->MaxY = 0;
        }
        if (Dest->MaxY >= SORT_GRID_HEIGHT) {
            Dest->MaxY = (SORT_GRID_HEIGHT - 1);
        }
    }
    return Inside;
}

uint32 BuildSpriteGraph(uint32 InputNodeCount, sort_sprite_bound *InputNodes, memory_arena *Arena,
                        uint32 ScreenWidth, uint32 ScreenHeight) {
    TIMED_FUNCTION();
#define ACCELERATED_SPRITE_SORT 1
    rectangle2 TotalScreen = RectMinMax(v2{0, 0}, v2i(ScreenWidth, ScreenHeight));
    sort_grid_entry *Grid[SORT_GRID_WIDTH][SORT_GRID_HEIGHT] = {};
    v2 InvCellDim = {(real32)SORT_GRID_WIDTH / (real32)ScreenWidth,
                     (real32)SORT_GRID_HEIGHT / (real32)ScreenHeight};
    uint32 NodeIndexA = 0;
    for (; NodeIndexA < InputNodeCount; ++NodeIndexA) {
        sort_sprite_bound *A = InputNodes + NodeIndexA;
        if (A->Offset == SPRITE_BARRIER_OFFSET_VALUE) {
            break;
        }
        Assert(A->Flags == 0);
        rectangle2i GridSpan;
        if (GetGridSpan(TotalScreen, InvCellDim, A->ScreenArea, &GridSpan)) {
            for (int32 GridX = GridSpan.MinX; GridX <= GridSpan.MaxX; ++GridX) {
                for (int32 GridY = GridSpan.MinY; GridY <= GridSpan.MaxY; ++GridY) {
                    sort_grid_entry *Entry = PushStruct(Arena, sort_grid_entry, NoClear());
                    Entry->Next = Grid[GridX][GridY];
                    Entry->OccupantIndex = NodeIndexA;
                    for (sort_grid_entry *EntryB = Grid[GridX][GridY]; EntryB;
                         EntryB = EntryB->Next) {
                        uint32 NodeIndexB = EntryB->OccupantIndex;
                        v2 Shrink{-4.0f, -4.0f};
                        sort_sprite_bound *B = InputNodes + NodeIndexB;
                        if ((B->Flags != NodeIndexA) &&
                            RectanglesIntersect(AddRadiusTo(A->ScreenArea, Shrink),
                                                AddRadiusTo(B->ScreenArea, Shrink))) {
                            Assert((NodeIndexA & Sprite_IndexMask) == NodeIndexA);
                            Assert((B->Flags & ~Sprite_IndexMask) == 0);
                            B->Flags = NodeIndexA;
                            uint32 FrontIndex = NodeIndexA;
                            uint32 BackIndex = NodeIndexB;

                            if (IsInFrontOf(B->SortKey, A->SortKey)) {
                                uint32 Temp = FrontIndex;
                                FrontIndex = BackIndex;
                                BackIndex = Temp;
                            }
                            (void)Arena;
                            sprite_edge *Edge = PushStruct(Arena, sprite_edge, NoClear());
                            sort_sprite_bound *Front = InputNodes + FrontIndex;
                            Edge->Front = FrontIndex;
                            Edge->Behind = BackIndex;

                            Edge->NextEdgeWithSameFront = Front->FirstEdgeWithMeAsFront;
                            Front->FirstEdgeWithMeAsFront = Edge;
                        }
                    }
                    Grid[GridX][GridY] = Entry;
                }
            }
        }
    }
    return NodeIndexA;
}

void RecursiveFontToBack(sprite_graph_walk *Walks, uint32 AtIndex) {
    sort_sprite_bound *At = Walks->InputNodes + AtIndex;
    Walks->HitCycle = Walks->HitCycle || (At->Flags & Sprite_Cycle);
    if (!(At->Flags & Sprite_Visited)) {
        At->Flags |= Sprite_Visited | Sprite_Cycle;
        for (sprite_edge *Edge = At->FirstEdgeWithMeAsFront; Edge;
             Edge = Edge->NextEdgeWithSameFront) {
            Assert(Edge->Front == AtIndex);
            RecursiveFontToBack(Walks, Edge->Behind);
        }
        if (!Walks->HitCycle) {
            At->Flags &= ~Sprite_Cycle;
        }
        *Walks->OutIndex++ = At->Offset;
    }
}
